#include<iostream>
#include<vector>
using namespace std;
/*
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
解题思路：
改题目转化为填满背包容量为m，n的背包的最大价值是多少，价值就是物品的个数，一个物品价值为1
改题目的背包容量是二维的m，n
所以可以构造一个二维dp数组dp[i][j]表示的含义是填满背包容量为i和j的背包的最大价值是多少
递推公式可以根据1维背包容量的0-1背包变换而来，dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1),
x和y为物品的0和1的个数（重量）
*/
int dp(vector<string> strs,int m,int n){
    //创建一个二维dp数组，背包容量为两个维度
    vector<vector<int>> dp(m+1,vector<int>(n+1));
    //初始化dp数组
    dp[0][0] = 0;
    //遍历dp数组先遍历物品再遍历背包
    for(string s:strs)
    {
        int x=0;
        int y=0;
        for(char c:s)
        {
            if(c=='0')
                x++;
            else
                y++;
        }
        //注意遍历背包容量时，由于背包容量是一个二维数组，所以要进行双重循环遍历
        for(int i=m;i>=x;i--)
        {
            for(int j=n;j>=y;j--)
            {
                dp[i][j] = max(dp[i][j],dp[i-x][j-y]+1);
            }
        }
    }
    return dp[m][n];
}

int main(){
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    vector<string> strs(number);
    cout<<"enter strs:"<<endl;
    for(int i=0;i<number;i++)
    {
        cin>>strs[i];
    }
    cout<<"enter m and n:"<<endl;
    int m,n;
    cin>>m>>n;
    cout<<dp(strs,m,n);
    return 0;
}